% !TEX TS-program = pdflatex
\documentclass[10pt, a4paper]{article}

\usepackage{a4wide}
\usepackage{color}
\usepackage{amsmath,amssymb,epsfig,pstricks,xspace}
\usepackage{german,graphics}
\usepackage{dsfont}
\usepackage{amsfonts}
\usepackage{graphics, psfrag}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{enumitem} 
\usepackage{url}
\usepackage{array,dcolumn,booktabs}
\usepackage{pdflscape}
\usepackage{amsthm}
\usepackage{ulem}

\newcounter{task}
\newcommand{\task}{\stepcounter{task}\paragraph{Task \thetask~--~
Solution\\}}

\usepackage{pifont}

\newcommand{\header}{
  \begin{center}
  \fbox{\parbox{11cm}{
    \begin{center}
      {\Large 3. Problem Session -- Solution\\ \vspace{0.2em}
        {\bf Secure Channels}\\ \vspace{0.7em} (Winter Term 2014/2015)\\
        \vspace{0.2em} \firstnameone \lastnameone\\
        \vspace{0.2em} \matriculationnumberone\\
        \vspace{0.2em} \firstnametwo \lastnametwo\\
        \vspace{0.2em} \matriculationnumbertwo \\
       \vspace{0.2em} \firstnamethree \lastnamethree\\
        \vspace{0.2em} \matriculationnumberthree
    }
    \end{center}
  }}
  \end{center}
}


%-------------------------------------------------------------------------------
%---------------------------- EDIT FROM HERE -----------------------------------
%-------------------------------------------------------------------------------

\newcommand{\firstnameone}{Jiaqi	}
\newcommand{\lastnameone}{Weng}
\newcommand{\matriculationnumberone}{115131}

\newcommand{\firstnametwo}{Vasilii	}
\newcommand{\lastnametwo}{Ponteleev}
\newcommand{\matriculationnumbertwo}{115151}

\newcommand{\firstnamethree}{Naveeni	}
\newcommand{\lastnamethree}{ Kumar Goswam}
\newcommand{\matriculationnumberthree}{113967}

\begin{document}
\pagestyle{plain}
\header


% number of tasks are automatically generated

\task
a)
set p is collision probability
if $0<q\leq 2^{l_1}$, p=0, because the count part not same.\\
if $q> 2^{l_1}$, collision happens when count part is same and random part is same as well.\\
for random part, it is a birthday bound problem,\\
 $N_r=2^{l_2}$, so the $p'\leq{q(q-1)/2*N}$, (p' is the probability of random part is same)\\
and the count part bound, \\
$p\leq p'*2^{l_1}=q(q-1)2^{l_1}/2*2^{l_2}$\\
q chose $(0, 2^{l_1}]$ could be better.\\
\\
b)\\
if NG do not call Init, \\
if $0<q\leq 2^{l_1}$, p=0,\\
if  $q> 2^{l_1}$, p=1.\\
q chose $(0, 2^{l_1}]$ could be better.\\
if NG call Init\\
set r is init times\\
like q times next(), it is also a birthday bound problem, and count part is always zero\\
$p\leq r(r-1)/2*2^{l_2}$

\task
For simplicity we consider only two blocks of plaintexts $P_1$, $P_2$ and corresponding ciphertexts $C_1$ , $C_2$. We know that 
$P_2$ should be well padded, which means C string message M terminates with 0 and remained bytes filled with random values like $MM0RRRRR$. We also can assume that bytes of message M cannot be 0. We can manipulate with $C_1$ and $C_2$ and send them to the oracle. We want to determine plain text which has been ciphered.
\\\\Let's take a look at CBC encryption wich is used to encrypt messages 
\\$C_1 = E_k( P_1 \oplus IV)$
\\$C_2 = E_k( P_2 \oplus C_1)$
\\\\Oracle will decrypt messages and check if padding is valid. So, we can try to manipulate the process by changing $C_1$ block to $C^{'}$. By sending $C^{'}$, $C_2$ to the oracle the following operations will be performed:
\\\\$P_2^{'} = D_k(C_2) \oplus C^{'}$
\\$P_1^{'} = D_k(C_1) \oplus IV$
\\\\Values $P_1^{'}$ and $P_2^{'}$ will be evaluated by the oracle (we cannot access them). Note that if $P_2^{'}$ is not well padded we will get an error.
\\\\Since $C_2 = E_k( P_2 \oplus C_1)$ we can gain more information from  $P_2^{'}$ 
\\$P_2^{'} = D_k( E_k( P_2 \oplus C_1)) \oplus C^{'} = P_2 \oplus C_1 \oplus C^{'}$
\\\\Now we try to determine $P_2$ and we only know $C_1$ and $C^{'}$, but padding oracle can provide us with an additional information if $P_2^{'}$ isn't well padded. 
\\\\We know that bytes of M cannot be zero, so we'll send pair  $C^{'}$, $C_2$ such as $C_1 \oplus C^{'} = 00...i$ where i = 0..0xff for every byte j of the block.
\\Wehenever we get an error we know that we changed byte of M to zero (according to our assumption bytes of M are not zeros), which means for j-th byte we have decrypted $P_2^{'}[j] = 0$, so
\\\\$P_2^{'}[j] = P_2[j] \oplus C_1[j] \oplus C^{'}[j]$
\\$0 = P_2[j] \oplus C_1[j] \oplus C^{'}[j]$
\\$P_2[j] = C_1[j] \oplus C^{'}[j]$
\\Since $C_1[j] \oplus C^{'}[j] = i$, $P_2[j] = i$
\\\\Byte by  byte we're decrypting the message. 
\\\\Note: this approach is based on a very strong assumption that turning byte M to 0 will cause an error. In the real world it would make more sense (since we're speaking about C world) after decryption take care of string termination, which means the last byte of message must be 0. If it isn't so, the error occures. It also means that our implementation wouldn't care about if M byte is 0 or not, the first 0 is the end of the message and that's it. In my opinion, this scenario should also be considered.
\\\\The thing is, it would be still possible to decrypt messages. The couple of operations should be changed to make it happen, but not the math.
\\\\First of all we need to find out which byte of original message is 0. It's quite similar to the process described above, with exception that i sould be equal 0xff. Once we have en error, we know the place where string terminates. (It also possible that there are several 0's in padding RRRR, but it only changes how sophisticated $C^{'}$ will be). 
\\\\Now our task is to make system happy. To do so we need to terminate string before the real $P_{2}s$ 0x00 by sending, for instance, $C_1 \oplus C^{'} = 0x00...0x$i$oxff...$ (oxff here prevents real $P_{2}s$ 0x00 byte to stop us). When the error dissappears we know that message is now terminated with 0x00 and we can use our equations. Then we repeat the same 1 byte left again and again until all message is discovered.


\task
a)
$E_k(0)=0$\\
\\Solution:
\\1. Choose N = 0, $C_0$ = 0
\\2. Choose $m_1$ = 0, $E_k(m_1)$ = $E_k (C_0 \oplus m_1 )$ = 0
\\Now, adversary ask from the oracle encryption of $E_k(m_1)$ . If the oracle
respond with 0 the adversary can say he is in real world and if the oracle
return anything other than 0 then adversary knows he is in random world.
It is quite trivial to see that adversary can predict between real and
random with high probability.
\\
b) \\
There exist a well known fix point X with $E_k(X)=X$\\
\\Solution:
\\1. Choose N = X, $C_0$ = X
\\2. Choose $m_1$ = 0, $E_k(m_1)$ = $E_k (C_0 \oplus m_1 )$ = X
\\Now, adversary can ask for the encryption of $E_k(X)$ if the oracle respond
with X, adversary will know he is in real world otherwise in random. So the
adversary can predict between real or random with high probability.
\\
c)\\
$\forall X: E_k(E_k(X))=X$\\
\\Solution : choose $m_1$ = 0 \& N = X, now adversary ask oracle the
encryption of $C_1$ , which should be equal to $C_0$ . Now if the oracle return
anything other than $C_0$ adversary will know he is in random world. In this
case too adversary can predict with high advantage between real and
random world.
\\
d)\\
$\forall{X} : E_k(\overline{X} ) = \overline{E_k(X )} $ where X is the bitwise complement of X, i.e., $X = X \oplus 1, . . . , 1$\\
Solution : adversary Choose message N as $\overline {X}$ and send it to oracle.  So
$C_0$ = $E_k(\overline X)$ , choose $m_1$ as 0. $C_1$ will be $E_k(\overline {X}$ ) .
\\Now in the second case adversary choose $N^{'}$ as X and choose message
$m_1^{'}$ as 0 and send it to the oracle, to get $C_1^{'}$ = $E_k(X \oplus 0 )$ .
\\Now adversary will do bitwise compliment of $C_1^{'}$ and check if the
compliment was equal to $C_1$ if the two values matches then adversary can
say he is in real world ( as $E_k(\overline X )$ = $\overline {E_k(X )}$ given ) else if the value doesnt
match adversary will know its random world. In this case too adversary
can easily predict between real and random with high probability.

\task
a) Assymetric schemes are not designed to perform encryption of large messages:
\\1)Symmetric encryption schemes are much faster and require less resources then assymetric ones.
\\2)Because assymetric scheme takes care of key distribution problem we don't need to worry about it in the case of distibution  symmetric $K_{se}$.
\\3)Since $K_{se}$ is exchanged between two parties using assymetric cryptography, we want to use $K_{se}$ during only one session to make sure that even $K_{se}$ is compromised it doesn't affect long-term key $K_p$. (Forward secrecy). It's much cheaper to generate new symmetric $K_{se}$ each time.
\\\\b)If client can't verify server's identity it will likely lead to several problems:
\\1) man in the middle scenario, where an adversary A will act as a server S for client C and as a client for a real server S.
\\2) spoofing, in case client connects to a fake adversary server, thinking that server is real. For instance, DNS poisoning, fake DNS, IP spoofing, etc.


\task
define adversary eve and MAC oracle.\\
eve send $(M, (A||1))$ to oracle, because MAC is secure MAC,\\
Pr[MAC(M)=A]=0, \\
eve send $(M', (A'||1))$ to oracle,\\
Pr[MAC'(M')=A']=Pr[MAC(M')||1 = A']= Pr[MAC(M') = A'(0,1,...n-1) and A'(n) = 1]\\
because Pr[MAC(M') = A'(0,1,...n-1)]=0, \\
Pr[MAC(M') = A'(0,1,...n-1) and A'(n) = 1] = 0.\\
\\
eve send $(M, (A||0))$ to oracle, because MAC is secure MAC,\\
Pr(MAC(M)=A and $m_1$ xor .....$m_n$=0)=0\\
eve send $(M', (A'||0))$ to oracle,\\
Pr[MAC'(M')=A' and $m_1$ xor .....$m_n$=0]\\
=Pr(MAC(M')||1=A' and $m_1$ xor .....$m_n$=0)\\
=Pr(A'(n)=1 and MAC(M')=A'(0,1,....n-1) and $m_1$ xor .....$m_n$=0)\\
because Pr(MAC(M')=A'(0,1,....n-1) and $m_1$ xor .....$m_n$=0)=0\\
Pr[MAC'(M')=A' and $m_1$ xor .....$m_n$=0]=0\\
so MAC' is secure MAC if MAC is secure MAC.






\end{document}
